﻿// 3771. 选取石子.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
/*
https://www.acwing.com/problem/content/3774/

给定 n
 个石子，编号为 1∼n
。

其中第 i
 个石子的价值为 ai
。

你需要从中任意挑选若干个石子，并将挑选好的石子按照编号从小到大的顺序排成一排。

选中的石子在排好序后需要满足，对于任意两个相邻的石子（不妨设它们的编号为 x,y
），x−y=ax−ay
 均成立。

例如，当有 n=8
 个石子，石子价值分别为 [3,4,4,6,6,7,8,9]
 时，一些合理的选择方案如下：

选择 1,2,4
 号石子，它们的价值分别为 3,4,6
。1
 号石子与 2
 号石子相邻，2−1=4−3
 成立。2
 号石子与 4
 号石子相邻，4−2=6−4
 成立。所以方案合理。
选择 7
 号石子。可以只选择一个石子，此时选取任何石子均为合理方案。
你的选择方案不仅需要合理，而且还要使得选中石子的价值总和尽可能大。

请计算并输出价值总和的最大可能值。

输入格式
第一行包含整数 n
。

第二行包含 n
 个整数 a1,a2,…,an
。

输出格式
一个整数，表示选中石子的价值总和的最大可能值。

数据范围
前三个测试点满足 1≤n≤10
。
全部测试点满足 1≤n≤2×105
，1≤ai≤4×105
。

输入样例1：
6
10 7 1 9 10 15
输出样例1：
26
输入样例2：
1
400000
输出样例2：
400000
输入样例3：
7
8 9 26 11 12 29 14
输出样例3：
55
*/
#include <iostream>

int main()
{
    std::cout << "Hello World!\n";
}

 